
// Definition for a Node.
class Node
{
public:
    int val;
    Node *next;

    Node() {}

    Node(int _val)
    {
        val = _val;
        next = nullptr;
    }

    Node(int _val, Node *_next)
    {
        val = _val;
        next = _next;
    }
};
//恶心模拟题
class Solution
{
public:
    Node *insert(Node *head, int insertVal)
    {
        //new一个待插入节点
        Node *new_node = new Node(insertVal);
        new_node->next = new_node;
        if (!head)
            return new_node;
        Node *cur = head->next;
        Node *pev = head;
        //枚举除了插入到最后一个点之后 的所有情况(该题没有不能插入的情况)
        while (cur != head)
        {
            //递增情况下的插入条件
            if (pev->val <= insertVal && cur->val >= insertVal)
                break;
            //边界情况要么新插入是最大要么是最小
            if (pev->val > cur->val && (insertVal < cur->val || insertVal > pev->val))
            {
                break;
            }
            pev = cur;
            cur = cur->next;
        }
        //插入
        new_node->next = pev->next;
        pev->next = new_node;
        return head;
    }
};